package com.my.study.algorithm.linked;

/**
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * 
 * 
 * @author Carlos
 * @version 1.0.0
 * @date 2023/4/4 7:44
 */
public class ReverseLinkK {

    public static ListNode reverseList(ListNode head, int k) {
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        
        // 创建一个哨兵节点
        ListNode dummy = new ListNode(-1, head);
        ListNode p0 = dummy;

        ListNode pre = null;
        cur = p0.next;
        while (len >= k) {
            len -= k;

            for (int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            
            ListNode next = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = next;
        }
        
        return dummy.next;
    }
    
}

